﻿/*
 *	Filename: wuyaowei_delete.c
 *	 Version: 0.1.0
 *   Description: 删除倒数第n个节点
 *
 *        Author: wuyaowei
 *          Date: 2020-06-13
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
  char data;
  struct Node * next;
}Node;

/*
 *  创建节点
 */
Node * createNode(char val) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->data = val;
  node->next = NULL;
  return node;
}

/*
 * 删除倒数第n个节点
 *
 * 使用两个指针，第一个指针从链表开头移动n+1步，
 * 第二个指针从链表开头移动，
 * 直到第一个指针移动到最后一个节点时，
 * 第二个指针指向倒数第n个节点。
 */

Node * deleteByNum(Node * head, int n) {
  Node *first = head;
  Node *second = head;

  while(n > 0) {
    first = first->next;
    n--;
  }

  Node *pre = NULL;

  if (first->next == NULL) {
    pre = head;
    head = head->next;
    free(pre);
    return head;
  }
  while(first->next != NULL) {
    pre = second;
    second = second->next;
    first = first->next;
  }

  pre->next = second->next;
  free(second);

  return head;
}


void main() {
  char str[100];
  int n = 0;
  Node *head = NULL;
  printf("输入链表数据：\n");
  scanf("%s",str);
  printf("输入删除的节点序号：\n");
  scanf("%d", &n);

  int len = strlen(str);

  //初始化单链表
  Node* p;
  for (int i = 0; i <= len; i++) {
       Node *t1 = createNode(str[i]);
       if (i == 0) {
         head = t1;
         p = t1;
         continue;	 
       }
       p->next = t1;
       p = t1;
  }

  head = deleteByNum(head, n);
  printf("删除后链表遍历输出:\n");
  while(NULL != head) {
     printf("%c ", head->data);
     head = head->next;
  }
  printf("\n");

}
